// 文件名：stack_bracket_matching.cpp
// 目的：用栈检查括号是否匹配与正确嵌套，支持 (), [], {} 三类括号。
// 算法：
//   - 遍历字符串：
//       * 遇到左括号入栈；
//       * 遇到右括号：若栈空或与栈顶不匹配则报错并返回 false，否则弹栈；
//   - 遍历结束后若栈非空，说明存在未闭合的括号；
//   - 否则返回 true。
// 诊断：
//   - 对首个不匹配的右括号，输出其位置与字符；
//   - 对未闭合情况，输出提示信息。
// 复杂度：O(N) 时间、O(N) 空间（最坏所有为左括号）。
// 注意：输入中非括号字符会被忽略（只处理三类括号）。

#include <iostream>
#include <stack>
#include <string>

bool checkBrackets(const std::string& s) {
    std::stack<char> st;
    auto isOpening = [](char c) {
        return c == '(' || c == '[' || c == '{';
    };
    auto matches = [](char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '[' && close == ']') ||
               (open == '{' && close == '}');
    };

    for (std::size_t i = 0; i < s.size(); ++i) {
        char c = s[i];
        if (isOpening(c)) {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty() || !matches(st.top(), c)) {
                std::cerr << "Mismatch at position " << i << ": " << c << '\n';
                return false;
            }
            st.pop();
        }
    }

    if (!st.empty()) {
        std::cerr << "Unclosed brackets remain.\n";
        return false;
    }
    return true;
}

int main() {
    std::string input = "{[()]()}";
    std::cout << input << " -> " << std::boolalpha << checkBrackets(input) << '\n';

    input = "{[(])}";
    std::cout << input << " -> " << std::boolalpha << checkBrackets(input) << '\n';

    return 0;
}